package com.cty.eightdDay;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/*
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序
 *
 * */
public class Q_9 {
    public static void main(String[] args) {
        String s = "sbbffafd";
        String p = "fbf";
        List<Integer> anagrams = findAnagrams3(s, p);
        System.out.println(Arrays.toString(anagrams.toArray()));
    }

    // 暴力解法 时间复杂度O(mn) 空间复杂度O(n) 自己写的恭喜一下主包吧
    public static List<Integer> findAnagrams(String s, String p) {
        if (s == null || s.length() == 0 || s.length() < p.length()) return new ArrayList<>();
        int n = s.length(), m = p.length();
        ArrayList<Integer> ans = new ArrayList<>();
        // 创建两个数组 用来记录s子串和p的字母的种类和数量
        int[] pChars = new int[26];
        int[] sChars = new int[26];
        // 记录p的字母数量和种类
        for (char c : p.toCharArray()) {
            pChars[c - 'a']++;
        }
        String sonStr;
        for (int i = 0; i < n - m + 1; i++) {
            sonStr = s.substring(i, i + m);
            Arrays.fill(sChars, 0);
            for (char c : sonStr.toCharArray()) {
                sChars[c - 'a']++;
            }
            if (isEqual(sChars, pChars)) {
                ans.add(i);
            }
        }
        return ans;
    }

    //判断两个数组是否相同
    public static boolean isEqual(int[] Arr1, int[] Arr2) {
        //因为传入的数组都是26的长度所以就不判断长度的大小了
        for (int i = 0; i < 26; i++) {
            if (Arr1[i] != Arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // 滑动窗口
    public static List<Integer> findAnagrams2(String s, String p) {
        if (s.length() < p.length()) return new ArrayList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        int pLen = p.length(), sLen = s.length();
        // 创建两个数组 用来
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; i++) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; i++) {
            //滑动窗口在滑动过程中先去掉最最左边的字母 加进最右端的字母
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(i + pLen) - 'a']++;

            if (Arrays.equals(sCount, pCount)) {
                // 两个数组相同 说明 刚添加进来的字母 和 去掉的字母相同 说明 i 的下一个字母是p的字母异位词的起始字母
                ans.add(i + 1);
            }
        }
        return ans;
    }

    // 优化滑动窗口 （力扣官方答案）
    public static List<Integer> findAnagrams3(String s, String p) {
        if (s.length() < p.length()) return new ArrayList<>();
        int sLen = s.length(), pLen = p.length();

        List<Integer> ans = new ArrayList<>();
        int[] count = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }

        int differ = 0;

        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) {
                ++differ;
            }
        }

        if (differ == 0) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            if (count[s.charAt(i) - 'a'] == 1) { //本来的计算数组中的是1表示与p有差距 但后面会减去1 这个差距就由不同变的相同
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {// 本来是0表示相同 后面减一变不同了
                ++differ;
            }
            --count[s.charAt(i) - 'a'];

            if (count[s.charAt(i + pLen) - 'a'] == -1) {//本来是-1表示不同 后面 +1 变相同了
                --differ;
            } else if (count[s.charAt(i + pLen) - 'a'] == 0) {//本来是0表示相同 后面 +1 变不同了
                ++differ;
            }
            ++count[s.charAt(i + pLen) - 'a'];

            if (differ == 0) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}
